1. Overview
In this notebook we will use clustering to transform a sample image to see how clustering can be used beyond simple data frames.
2. Libraries
A new library will be installed and used - imager
library(imager)
package 㤼㸱imager㤼㸲 was built under R version 3.5.1Loading required package: magrittr
Attaching package: 㤼㸱imager㤼㸲
The following object is masked from 㤼㸱package:magrittr㤼㸲:
add
The following objects are masked from 㤼㸱package:stats㤼㸲:
convolve, spectrum
The following object is masked from 㤼㸱package:graphics㤼㸲:
frame
The following object is masked from 㤼㸱package:base㤼㸲:
save.image
3. Loading sample image
This function will load a sample image from a file or URL using imager library and store it as CIMG file (Effectively being a very large string of numbers).
Display function will show you the picture in the separate window
More information can be found under: https://cran.r-project.org/web/packages/imager/vignettes/gettingstarted.html
image <-load.image("FRABEL.jpg")
display(image)
5. Sneak peek onto the image
The easiest way to see the image is to use ggplot function and draw it as a plot. For this we need to use ggplot2 library
However, first we need to convert data from RGB to HEX to allow computer to understand what colour to use. For this, we will use “rgb” function and store it as a separate value under imgcolour variable.
imgcolour <- rgb(pivotimage[c("R","G","B")])
Now we can plot the image using ggplot function
library(ggplot2)
package 㤼㸱ggplot2㤼㸲 was built under R version 3.5.1
ggplot(data=pivotimage)+
aes(x=x, y=-y)+
geom_point(colour=imgcolour)+
coord_fixed()

ggplot function allows you to do many things, but you need to specify every parameter (as oppose to qplot function for example). Remember to use “+” sign to add another parameter
data = dataframe - in this case reshaped one (pivotimage)
aes allows to specify aesthetics and dimensions. In this case it’s easy (x and y), but you need to be vary that you need to reverse y value (-y)
geom allows to define the shae of the graph and add parameters to this shape. In our case geom_point is best suited as it plots dots with colors defined in “colour” parameter. Colour should equal newly created HEX values so that the program will know what HEX value each pixel should have.
coord_fixed parameter allows to fix the ratio for both axis - otherwise the picture could look too wide or too narrow.
6. Working with k-means - clustering
Here we are going to create clusters for our image using k-means algorithm and function.
First we need to define the number of clusters that we want to have - let’s choose 3 and store it under a new variable
kparameter <- 4
Then we need to define imgCluster variable that will store all rows from the pivot table but only RGB columns
imgCluster <- data.frame(pivotimage$R, pivotimage$G, pivotimage$B)
head(imgCluster)
Now we’re going to use k-means to find centroids for us. These are shown below and represents most important colours on the image
kmeansresults <- kmeans(imgCluster, centers = kparameter)
kmeansresults$centers
pivotimage.R pivotimage.G pivotimage.B
1 0.4456714 0.5201895 0.2536242
2 0.6946025 0.7333159 0.7122830
3 0.1641468 0.1501433 0.1441674
4 0.8261590 0.2229151 0.1736795
K-means also created clusters for each pixel so we can group pixels together. Now adding newly created groups to each pixel
pivotimage$Cluster <- kmeansresults$cluster
7. Cluster visualisation
This is how you can visualize the results of the clustering. To do that we will use some functions from “plotly” library so you’d need to install it first.
First we need to convert centroids found from RGB onto HEX using rgb function.
ClusterColours <- rgb(kmeansresults$centers)
ClusterColours
[1] "#728541" "#B1BBB6" "#2A2625" "#D3392C"
Now we have got colours of these centroids and we can use plot function to view them. This code block will plot rectangular boxes in each color (centroid) with a name of the cluster in it.
SetTextContrastColor <- function(color)
{
ifelse( mean(col2rgb(color)) > 127, "black", "white")}
##Function above will allow you to define whether to set the color of the cluster name in white or black depending on the cluster colour (if dark then white label and vice versa)
plot(0, type = "n", axes = FALSE, ylab = "", xlab = "", ylim = c(2,0), xlim = c(0,5))
title("Clusters as colours")
##Plotting a space without data (0), type n, axes not visible and with size 5 in width and size 2 height
for (i in 0:(kparameter-1)) {
rect(i,0,i+1,1,col=ClusterColours[i+1])
text(i+0.5,0.5, i+1, col=SetTextContrastColor(ClusterColours[i+1]))}

##This loop function will plot rectangulars in colors of clusters and labels on the previously created space.
Now we’re adding cluster group to each point in the imgCluster frame based on centroids found using k-means
imgCluster$cluster <-kmeansresults$cluster
head(imgCluster)
Now we’re ready to plot some more ..
library(plotly)
imgPivotSample <- pivotimage[sample(1:nrow(pivotimage), 1000, replace=FALSE),]
##Creating a sample of points from the image (processing of the full image might crash computer as it has millions of pixels)
plot <- plot_ly(
imgPivotSample, x = ~R, y = ~G, z = ~B,
##Take sample of 1000 points and for each point - imgPivotSample
## For each dimension x,y,z assign one colour (R,G,B) so RGB would be coordinates on the 3D plot
color = ~Cluster,
## Color parameter takes the value from the cluster column for each point and plot this point in a colour of the cluster
colors = rgb(kmeansresults$centers),
## colors parameter shows a vector of colours in HEX format (after converting centroids using rgb function)
marker = list(symbol = "circle", size = 4)
## marker parameter sets point type and size
) %>%
add_markers() %>%
layout(
scene = list(xaxis = list(title = 'Red', color='#FF0000'),
yaxis = list(title = 'Green', color='#00FF00'),
zaxis = list(title = 'Blue', color='#0000FF'))
)
##Add markers function adds colours to each axis in line with its name - red, green, blue
plot
problem creating directory C:\Users\dserwinowski\OneDrive - Burberry Ltd\Data Fellowship\Clustering\Clustering exercise with image\.Rproj.user\shared\notebooks\98E89FF2-Clustering exercise with image\1\42B2BA218811B71D\crjbed3sk21nx_t\lib\plotly-binding-4.7.1\lib\colourpicker: No such file or directoryover-long path lengthover-long path lengthover-long path lengthover-long path lengthover-long path length
##Plots the variable created using plot_ly
8. Fine tuning k-means
This chapter is to fine tune k-means to see how many clusters are optimal for the chosen image. For this we will use WSS (within cluster sum of squares) method.
kparameterMax <- 10
##Set the max number of clusters possible
wss <- sapply(1:kparameterMax,
function(k){kmeans(pivotimage[c("R", "G", "B")], k)$tot.withinss})
##Calculate wss for different number of clusters for our image stored under pivotimage and store it under "wss" variable
plot(1:kparameterMax, wss,
type="b", pch = 19, frame = FALSE,
xlab="Number of clusters K",
ylab="Total within-clusters sum of squares")
##This is to plot the line graph of wss variable to spot the elbow - the optimum number of clusters
abline (v=4, lty=2)

9. Recolour the image
Here we will recolour the image using centroids found only - so only 4 colours on the entire picture will be used. Each point from the image will be recoloured by the colour of its centroid depending on the cluster it’s in.
First create a new variable that will allow to store “reimaged” image by converting each point to the color of its cluster and use rgb function to convert it to HEX
kColours <- rgb(kmeansresults$centers[pivotimage$Cluster,])
Then plot it using ggplot
ggplot(data = pivotimage, aes(x = x, y = -y)) + geom_point(colour = kColours) + coord_fixed()

10. Instagram-like filter? Why not?
So now we know how to find centroids and apply it to the image. Why not making it more Instagram-like and choose one colour and make the ret of the image greyscale? We need to choose one cluster - maybe red? So number 4.
Now we will recolour our image leaving red and turining everything else onto greyscale. However first we need to create a function that will determine it - it will be called “color_or_grey”
clusterLabel <- 4
grey_scale <- function(colour){
grey <- colour[1] * 0.2126 + colour[2] * 0.7152 + colour[3] * 0.0722
return(rgb(grey,grey,grey))}
## this is how the colour is converted to greyscale
color_or_grey <- function(row){
if(row["Cluster"]==clusterLabel){
return(rgb(row["R"],row["G"],row["B"]))
}
else{
return(grey_scale(as.numeric(row[c("R","G","B")])))
}
}
pivotimage$splash <- apply(pivotimage,1,color_or_grey)
## Then we can assign a new variable and run the apply function to check and convert it for us
and plot it…
ggplot(data = pivotimage, aes(x = x, y = -y)) + geom_point(colour = pivotimage$splash) + coord_fixed()

LS0tDQp0aXRsZTogIkNsdXN0ZXJpbmcgSUkiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIDEuIE92ZXJ2aWV3DQpJbiB0aGlzIG5vdGVib29rIHdlIHdpbGwgdXNlIGNsdXN0ZXJpbmcgdG8gdHJhbnNmb3JtIGEgc2FtcGxlIGltYWdlIHRvIHNlZSBob3cgY2x1c3RlcmluZyBjYW4gYmUgdXNlZCBiZXlvbmQgc2ltcGxlIGRhdGEgZnJhbWVzLg0KDQojIDIuIExpYnJhcmllcw0KQSBuZXcgbGlicmFyeSB3aWxsIGJlIGluc3RhbGxlZCBhbmQgdXNlZCAtIGltYWdlcg0KYGBge3J9DQpsaWJyYXJ5KGltYWdlcikNCmBgYA0KICANCiMgMy4gTG9hZGluZyBzYW1wbGUgaW1hZ2UNClRoaXMgZnVuY3Rpb24gd2lsbCBsb2FkIGEgc2FtcGxlIGltYWdlIGZyb20gYSBmaWxlIG9yIFVSTCB1c2luZyBpbWFnZXIgbGlicmFyeSBhbmQgc3RvcmUgaXQgYXMgQ0lNRyBmaWxlIChFZmZlY3RpdmVseSBiZWluZyBhIHZlcnkgbGFyZ2Ugc3RyaW5nIG9mIG51bWJlcnMpLg0KDQpEaXNwbGF5IGZ1bmN0aW9uIHdpbGwgc2hvdyB5b3UgdGhlIHBpY3R1cmUgaW4gdGhlIHNlcGFyYXRlIHdpbmRvdw0KDQpNb3JlIGluZm9ybWF0aW9uIGNhbiBiZSBmb3VuZCB1bmRlcjoNCmh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9pbWFnZXIvdmlnbmV0dGVzL2dldHRpbmdzdGFydGVkLmh0bWwNCg0KYGBge3J9DQppbWFnZSA8LWxvYWQuaW1hZ2UoIkZSQUJFTC5qcGciKQ0KZGlzcGxheShpbWFnZSkNCmBgYA0KDQojIDQuIFJlZm9ybWF0dGluZyBhbiBpbWFnZQ0KSGVyZSB3ZSB3aWxsIHRyYW5zZm9ybSB0aGUgZGF0YSBmcm9tIGFuIGltYWdlIHRvIGEgZGF0YWZyYW1lIHNvIGl0IGNhbiBiZSByZWFkIGFzIGEgYnVuY2ggb2YgUkdCIChyZWQsIGdyZWVuLCBibHVlKSB2YWx1ZXMgZm9yIGEgc2luZ2xlIHBpeGVsLiBUSGlzIGlzIGFjdHVhbGx5IGhvdyBhIGNvbXB1dGVyIHN0b3JlcyBhbiBpbWFnZS4NCiAgDQoNCmBgYHtyfQ0KZGZpbWFnZSA8LSBhcy5kYXRhLmZyYW1lKGltYWdlKQ0KaGVhZChkZmltYWdlKQ0KYGBgDQogIA0KDQp4IC0gd2lkdGggIA0KeSAtIGhlaWdodCAgDQpjYyAtIGRlcHRoICANCnZhbHVlIC0gY29sb3VyIGNoYW5uZWwgIA0KICANCg0KVGhlIGZ1bmN0aW9uIGJlbG93IHJlc2hhcGUgKHRyYW5zZm9ybXMpIHRoZSBkYXRhIGZyYW1lIG9udG8gYSBwaXZvdCB0YWJsZSB0aGF0IHdpbGwgc2hvdyBSR0IgdmFsdWVzIGZvciBlYWNoIHBpeGVsIGFuZCB0dXJucyBpbnRvIGEgIndpZGUiIHBpY3R1cmUNCg0KYGBge3J9DQpwaXZvdGltYWdlIDwtIHJlc2hhcGUoZGZpbWFnZSwgZGlyZWN0aW9uID0gIndpZGUiLCB0aW1ldmFyID0gImNjIiwgaWR2YXIgPSBjKCJ4IiwgInkiKSkNCmhlYWQocGl2b3RpbWFnZSkNCmBgYA0KICANCg0KQWZ0ZXIgcmVzaGFwaW5nIC0gd2UgbmVlZCB0byByZW5hbWUgY29sdW1ucyBhcyBwZXIgdGhlIFJHQiBjb252ZW50aW9uIChhcyB0aGVzZSB2YWx1ZXMgcmVsYXRlIHRvIHRoZSBkZW5zaXR5IG9mIGVhY2ggY29sb3VyIGluIHRoZSBjb2xvdXIgbWl4KQ0KDQpgYGB7cn0NCm5hbWVzKHBpdm90aW1hZ2UpWzNdIDwtICJSIg0KbmFtZXMocGl2b3RpbWFnZSlbNF0gPC0gIkciDQpuYW1lcyhwaXZvdGltYWdlKVs1XSA8LSAiQiINCmhlYWQocGl2b3RpbWFnZSkNCg0KYGBgDQoNCiMgNS4gU25lYWsgcGVlayBvbnRvIHRoZSBpbWFnZQ0KVGhlIGVhc2llc3Qgd2F5IHRvIHNlZSB0aGUgaW1hZ2UgaXMgdG8gdXNlIGdncGxvdCBmdW5jdGlvbiBhbmQgZHJhdyBpdCBhcyBhIHBsb3QuIEZvciB0aGlzIHdlIG5lZWQgdG8gdXNlIGdncGxvdDIgbGlicmFyeQ0KICANCkhvd2V2ZXIsIGZpcnN0IHdlIG5lZWQgdG8gY29udmVydCBkYXRhIGZyb20gUkdCIHRvIEhFWCB0byBhbGxvdyBjb21wdXRlciB0byB1bmRlcnN0YW5kIHdoYXQgY29sb3VyIHRvIHVzZS4gRm9yIHRoaXMsIHdlIHdpbGwgdXNlICJyZ2IiIGZ1bmN0aW9uIGFuZCBzdG9yZSBpdCBhcyBhIHNlcGFyYXRlIHZhbHVlIHVuZGVyIGltZ2NvbG91ciB2YXJpYWJsZS4gDQoNCmBgYHtyfQ0KaW1nY29sb3VyIDwtIHJnYihwaXZvdGltYWdlW2MoIlIiLCJHIiwiQiIpXSkNCmBgYA0KICANCk5vdyB3ZSBjYW4gcGxvdCB0aGUgaW1hZ2UgdXNpbmcgZ2dwbG90IGZ1bmN0aW9uDQpgYGB7cn0NCmxpYnJhcnkoZ2dwbG90MikNCmdncGxvdChkYXRhPXBpdm90aW1hZ2UpKw0KICBhZXMoeD14LCB5PS15KSsNCiAgZ2VvbV9wb2ludChjb2xvdXI9aW1nY29sb3VyKSsNCiAgY29vcmRfZml4ZWQoKQ0KYGBgDQogIA0KX19nZ3Bsb3RfXyBmdW5jdGlvbiBhbGxvd3MgeW91IHRvIGRvIG1hbnkgdGhpbmdzLCBidXQgeW91IG5lZWQgdG8gc3BlY2lmeSBldmVyeSBwYXJhbWV0ZXIgKGFzIG9wcG9zZSB0byBxcGxvdCBmdW5jdGlvbiBmb3IgZXhhbXBsZSkuIFJlbWVtYmVyIHRvIHVzZSAiKyIgc2lnbiB0byBhZGQgYW5vdGhlciBwYXJhbWV0ZXIgIA0KX19kYXRhX18gPSBkYXRhZnJhbWUgLSBpbiB0aGlzIGNhc2UgcmVzaGFwZWQgb25lIChwaXZvdGltYWdlKSAgDQpfX2Flc19fIGFsbG93cyB0byBzcGVjaWZ5IGFlc3RoZXRpY3MgYW5kIGRpbWVuc2lvbnMuIEluIHRoaXMgY2FzZSBpdCdzIGVhc3kgKHggYW5kIHkpLCBidXQgeW91IG5lZWQgdG8gYmUgdmFyeSB0aGF0IHlvdSBuZWVkIHRvIHJldmVyc2UgeSB2YWx1ZSAoLXkpICANCl9fZ2VvbV9fIGFsbG93cyB0byBkZWZpbmUgdGhlIHNoYWUgb2YgdGhlIGdyYXBoIGFuZCBhZGQgcGFyYW1ldGVycyB0byB0aGlzIHNoYXBlLiBJbiBvdXIgY2FzZSBnZW9tX3BvaW50IGlzIGJlc3Qgc3VpdGVkIGFzIGl0IHBsb3RzIGRvdHMgd2l0aCBjb2xvcnMgZGVmaW5lZCBpbiAiY29sb3VyIiBwYXJhbWV0ZXIuIENvbG91ciBzaG91bGQgZXF1YWwgbmV3bHkgY3JlYXRlZCBIRVggdmFsdWVzIHNvIHRoYXQgdGhlIHByb2dyYW0gd2lsbCBrbm93IHdoYXQgSEVYIHZhbHVlIGVhY2ggcGl4ZWwgc2hvdWxkIGhhdmUuICAgDQpfX2Nvb3JkX2ZpeGVkX18gcGFyYW1ldGVyIGFsbG93cyB0byBmaXggdGhlIHJhdGlvIGZvciBib3RoIGF4aXMgLSBvdGhlcndpc2UgdGhlIHBpY3R1cmUgY291bGQgbG9vayB0b28gd2lkZSBvciB0b28gbmFycm93LiAgDQoNCg0KIzYuIFdvcmtpbmcgd2l0aCBrLW1lYW5zIC0gY2x1c3RlcmluZw0KSGVyZSB3ZSBhcmUgZ29pbmcgdG8gY3JlYXRlIGNsdXN0ZXJzIGZvciBvdXIgaW1hZ2UgdXNpbmcgay1tZWFucyBhbGdvcml0aG0gYW5kIGZ1bmN0aW9uLiANCg0KRmlyc3Qgd2UgbmVlZCB0byBkZWZpbmUgdGhlIG51bWJlciBvZiBjbHVzdGVycyB0aGF0IHdlIHdhbnQgdG8gaGF2ZSAtIGxldCdzIGNob29zZSAzIGFuZCBzdG9yZSBpdCB1bmRlciBhIG5ldyB2YXJpYWJsZQ0KDQpgYGB7cn0NCmtwYXJhbWV0ZXIgPC0gNA0KYGBgDQogIA0KVGhlbiB3ZSBuZWVkIHRvIGRlZmluZSBpbWdDbHVzdGVyIHZhcmlhYmxlIHRoYXQgd2lsbCBzdG9yZSBhbGwgcm93cyBmcm9tIHRoZSBwaXZvdCB0YWJsZSBidXQgb25seSBSR0IgY29sdW1ucw0KYGBge3J9DQppbWdDbHVzdGVyIDwtIGRhdGEuZnJhbWUocGl2b3RpbWFnZSRSLCBwaXZvdGltYWdlJEcsIHBpdm90aW1hZ2UkQikNCmhlYWQoaW1nQ2x1c3RlcikNCmBgYA0KDQpOb3cgd2UncmUgZ29pbmcgdG8gdXNlIGstbWVhbnMgdG8gZmluZCBjZW50cm9pZHMgZm9yIHVzLiBUaGVzZSBhcmUgc2hvd24gYmVsb3cgYW5kIHJlcHJlc2VudHMgbW9zdCBpbXBvcnRhbnQgY29sb3VycyBvbiB0aGUgaW1hZ2UNCmBgYHtyfQ0Ka21lYW5zcmVzdWx0cyA8LSBrbWVhbnMoaW1nQ2x1c3RlciwgY2VudGVycyA9IGtwYXJhbWV0ZXIpDQprbWVhbnNyZXN1bHRzJGNlbnRlcnMNCmBgYA0KICANCkstbWVhbnMgYWxzbyBjcmVhdGVkIGNsdXN0ZXJzIGZvciBlYWNoIHBpeGVsIHNvIHdlIGNhbiBncm91cCBwaXhlbHMgdG9nZXRoZXIuIE5vdyBhZGRpbmcgbmV3bHkgY3JlYXRlZCBncm91cHMgdG8gZWFjaCBwaXhlbA0KYGBge3J9DQpwaXZvdGltYWdlJENsdXN0ZXIgPC0ga21lYW5zcmVzdWx0cyRjbHVzdGVyDQpgYGANCg0KIzcuIENsdXN0ZXIgdmlzdWFsaXNhdGlvbg0KVGhpcyBpcyBob3cgeW91IGNhbiB2aXN1YWxpemUgdGhlIHJlc3VsdHMgb2YgdGhlIGNsdXN0ZXJpbmcuIFRvIGRvIHRoYXQgd2Ugd2lsbCB1c2Ugc29tZSBmdW5jdGlvbnMgZnJvbSAicGxvdGx5IiBsaWJyYXJ5IHNvIHlvdSdkIG5lZWQgdG8gaW5zdGFsbCBpdCBmaXJzdC4NCiAgDQpGaXJzdCB3ZSBuZWVkIHRvIGNvbnZlcnQgY2VudHJvaWRzIGZvdW5kIGZyb20gUkdCIG9udG8gSEVYIHVzaW5nIHJnYiBmdW5jdGlvbi4NCmBgYHtyfQ0KQ2x1c3RlckNvbG91cnMgPC0gcmdiKGttZWFuc3Jlc3VsdHMkY2VudGVycykNCkNsdXN0ZXJDb2xvdXJzDQpgYGANCiAgDQpOb3cgd2UgaGF2ZSBnb3QgY29sb3VycyBvZiB0aGVzZSBjZW50cm9pZHMgYW5kIHdlIGNhbiB1c2UgcGxvdCBmdW5jdGlvbiB0byB2aWV3IHRoZW0uIFRoaXMgY29kZSBibG9jayB3aWxsIHBsb3QgcmVjdGFuZ3VsYXIgYm94ZXMgaW4gZWFjaCBjb2xvciAoY2VudHJvaWQpIHdpdGggYSBuYW1lIG9mIHRoZSBjbHVzdGVyIGluIGl0LiANCg0KYGBge3J9DQpTZXRUZXh0Q29udHJhc3RDb2xvciA8LSBmdW5jdGlvbihjb2xvcikNCnsNCiAgaWZlbHNlKCBtZWFuKGNvbDJyZ2IoY29sb3IpKSA+IDEyNywgImJsYWNrIiwgIndoaXRlIil9DQojI0Z1bmN0aW9uIGFib3ZlIHdpbGwgYWxsb3cgeW91IHRvIGRlZmluZSB3aGV0aGVyIHRvIHNldCB0aGUgY29sb3Igb2YgdGhlIGNsdXN0ZXIgbmFtZSBpbiB3aGl0ZSBvciBibGFjayBkZXBlbmRpbmcgb24gdGhlIGNsdXN0ZXIgY29sb3VyIChpZiBkYXJrIHRoZW4gd2hpdGUgbGFiZWwgYW5kIHZpY2UgdmVyc2EpDQoNCg0KcGxvdCgwLCB0eXBlID0gIm4iLCBheGVzID0gRkFMU0UsIHlsYWIgPSAiIiwgeGxhYiA9ICIiLCB5bGltID0gYygyLDApLCB4bGltID0gYygwLDUpKQ0KdGl0bGUoIkNsdXN0ZXJzIGFzIGNvbG91cnMiKQ0KIyNQbG90dGluZyBhIHNwYWNlIHdpdGhvdXQgZGF0YSAoMCksIHR5cGUgbiwgYXhlcyBub3QgdmlzaWJsZSBhbmQgd2l0aCBzaXplIDUgaW4gd2lkdGggYW5kIHNpemUgMiBoZWlnaHQNCg0KZm9yIChpIGluIDA6KGtwYXJhbWV0ZXItMSkpIHsNCiAgcmVjdChpLDAsaSsxLDEsY29sPUNsdXN0ZXJDb2xvdXJzW2krMV0pDQogIHRleHQoaSswLjUsMC41LCBpKzEsIGNvbD1TZXRUZXh0Q29udHJhc3RDb2xvcihDbHVzdGVyQ29sb3Vyc1tpKzFdKSl9DQojI1RoaXMgbG9vcCBmdW5jdGlvbiB3aWxsIHBsb3QgcmVjdGFuZ3VsYXJzIGluIGNvbG9ycyBvZiBjbHVzdGVycyBhbmQgbGFiZWxzIG9uIHRoZSBwcmV2aW91c2x5IGNyZWF0ZWQgc3BhY2UuIA0KDQpgYGANCg0KTm93IHdlJ3JlIGFkZGluZyBjbHVzdGVyIGdyb3VwIHRvIGVhY2ggcG9pbnQgaW4gdGhlIGltZ0NsdXN0ZXIgZnJhbWUgYmFzZWQgb24gY2VudHJvaWRzIGZvdW5kIHVzaW5nIGstbWVhbnMNCmBgYHtyfQ0KaW1nQ2x1c3RlciRjbHVzdGVyIDwta21lYW5zcmVzdWx0cyRjbHVzdGVyDQpoZWFkKGltZ0NsdXN0ZXIpDQpgYGANCg0KTm93IHdlJ3JlIHJlYWR5IHRvIHBsb3Qgc29tZSBtb3JlIC4uDQoNCg0KYGBge3J9DQpsaWJyYXJ5KHBsb3RseSkNCmltZ1Bpdm90U2FtcGxlIDwtIHBpdm90aW1hZ2Vbc2FtcGxlKDE6bnJvdyhwaXZvdGltYWdlKSwgMTAwMCwgcmVwbGFjZT1GQUxTRSksXQ0KIyNDcmVhdGluZyBhIHNhbXBsZSBvZiBwb2ludHMgZnJvbSB0aGUgaW1hZ2UgKHByb2Nlc3Npbmcgb2YgdGhlIGZ1bGwgaW1hZ2UgbWlnaHQgY3Jhc2ggY29tcHV0ZXIgYXMgaXQgaGFzIG1pbGxpb25zIG9mIHBpeGVscykNCg0KcGxvdCA8LSBwbG90X2x5KA0KICAgIGltZ1Bpdm90U2FtcGxlLCB4ID0gflIsIHkgPSB+RywgeiA9IH5CLA0KIyNUYWtlIHNhbXBsZSBvZiAxMDAwIHBvaW50cyBhbmQgZm9yIGVhY2ggcG9pbnQgLSBpbWdQaXZvdFNhbXBsZQ0KIyMgRm9yIGVhY2ggZGltZW5zaW9uIHgseSx6IGFzc2lnbiBvbmUgY29sb3VyIChSLEcsQikgc28gUkdCIHdvdWxkIGJlIGNvb3JkaW5hdGVzIG9uIHRoZSAzRCBwbG90DQogICAgY29sb3IgPSB+Q2x1c3RlciwgDQojIyBDb2xvciBwYXJhbWV0ZXIgdGFrZXMgdGhlIHZhbHVlIGZyb20gdGhlIGNsdXN0ZXIgY29sdW1uIGZvciBlYWNoIHBvaW50IGFuZCBwbG90IHRoaXMgcG9pbnQgaW4gYSBjb2xvdXIgb2YgdGhlIGNsdXN0ZXIgDQogICAgY29sb3JzID0gcmdiKGttZWFuc3Jlc3VsdHMkY2VudGVycyksDQojIyBjb2xvcnMgcGFyYW1ldGVyIHNob3dzIGEgdmVjdG9yIG9mIGNvbG91cnMgaW4gSEVYIGZvcm1hdCAoYWZ0ZXIgY29udmVydGluZyBjZW50cm9pZHMgdXNpbmcgcmdiIGZ1bmN0aW9uKQ0KICAgIG1hcmtlciA9IGxpc3Qoc3ltYm9sID0gImNpcmNsZSIsIHNpemUgPSA0KQ0KIyMgbWFya2VyIHBhcmFtZXRlciBzZXRzIHBvaW50IHR5cGUgYW5kIHNpemUNCiAgKSAlPiUNCiAgYWRkX21hcmtlcnMoKSAlPiUNCiAgbGF5b3V0KA0KICAgIHNjZW5lID0gbGlzdCh4YXhpcyA9IGxpc3QodGl0bGUgPSAnUmVkJywgY29sb3I9JyNGRjAwMDAnKSwNCiAgICAgICAgICAgICAgICAgeWF4aXMgPSBsaXN0KHRpdGxlID0gJ0dyZWVuJywgY29sb3I9JyMwMEZGMDAnKSwNCiAgICAgICAgICAgICAgICAgemF4aXMgPSBsaXN0KHRpdGxlID0gJ0JsdWUnLCBjb2xvcj0nIzAwMDBGRicpKQ0KICApDQojI0FkZCBtYXJrZXJzIGZ1bmN0aW9uIGFkZHMgY29sb3VycyB0byBlYWNoIGF4aXMgaW4gbGluZSB3aXRoIGl0cyBuYW1lIC0gcmVkLCBncmVlbiwgYmx1ZQ0KDQpwbG90DQojI1Bsb3RzIHRoZSB2YXJpYWJsZSBjcmVhdGVkIHVzaW5nIHBsb3RfbHkNCg0KYGBgDQoNCiM4LiBGaW5lIHR1bmluZyBrLW1lYW5zDQpUaGlzIGNoYXB0ZXIgaXMgdG8gZmluZSB0dW5lIGstbWVhbnMgdG8gc2VlIGhvdyBtYW55IGNsdXN0ZXJzIGFyZSBvcHRpbWFsIGZvciB0aGUgY2hvc2VuIGltYWdlLiBGb3IgdGhpcyB3ZSB3aWxsIHVzZSBXU1MgKHdpdGhpbiBjbHVzdGVyIHN1bSBvZiBzcXVhcmVzKSBtZXRob2QuIA0KDQoNCmBgYHtyfQ0Ka3BhcmFtZXRlck1heCA8LSAxMA0KIyNTZXQgdGhlIG1heCBudW1iZXIgb2YgY2x1c3RlcnMgcG9zc2libGUNCg0Kd3NzIDwtIHNhcHBseSgxOmtwYXJhbWV0ZXJNYXgsDQogICAgICAgIGZ1bmN0aW9uKGspe2ttZWFucyhwaXZvdGltYWdlW2MoIlIiLCAiRyIsICJCIildLCBrKSR0b3Qud2l0aGluc3N9KQ0KIyNDYWxjdWxhdGUgd3NzIGZvciBkaWZmZXJlbnQgbnVtYmVyIG9mIGNsdXN0ZXJzIGZvciBvdXIgaW1hZ2Ugc3RvcmVkIHVuZGVyIHBpdm90aW1hZ2UgYW5kIHN0b3JlIGl0IHVuZGVyICJ3c3MiIHZhcmlhYmxlDQoNCnBsb3QoMTprcGFyYW1ldGVyTWF4LCB3c3MsDQogICAgICAgdHlwZT0iYiIsIHBjaCA9IDE5LCBmcmFtZSA9IEZBTFNFLA0KICAgICAgIHhsYWI9Ik51bWJlciBvZiBjbHVzdGVycyBLIiwNCiAgICAgICB5bGFiPSJUb3RhbCB3aXRoaW4tY2x1c3RlcnMgc3VtIG9mIHNxdWFyZXMiKQ0KIyNUaGlzIGlzIHRvIHBsb3QgdGhlIGxpbmUgZ3JhcGggb2Ygd3NzIHZhcmlhYmxlIHRvIHNwb3QgdGhlIGVsYm93IC0gdGhlIG9wdGltdW0gbnVtYmVyIG9mIGNsdXN0ZXJzDQoNCmFibGluZSAodj00LCBsdHk9MikNCmBgYA0KDQoNCiM5LiBSZWNvbG91ciB0aGUgaW1hZ2UNCkhlcmUgd2Ugd2lsbCByZWNvbG91ciB0aGUgaW1hZ2UgdXNpbmcgY2VudHJvaWRzIGZvdW5kIG9ubHkgLSBzbyBvbmx5IDQgY29sb3VycyBvbiB0aGUgZW50aXJlIHBpY3R1cmUgd2lsbCBiZSB1c2VkLiBFYWNoIHBvaW50IGZyb20gdGhlIGltYWdlIHdpbGwgYmUgcmVjb2xvdXJlZCBieSB0aGUgY29sb3VyIG9mIGl0cyBjZW50cm9pZCBkZXBlbmRpbmcgb24gdGhlIGNsdXN0ZXIgaXQncyBpbi4NCiAgDQpGaXJzdCBjcmVhdGUgYSBuZXcgdmFyaWFibGUgdGhhdCB3aWxsIGFsbG93IHRvIHN0b3JlICJyZWltYWdlZCIgaW1hZ2UgYnkgY29udmVydGluZyBlYWNoIHBvaW50IHRvIHRoZSBjb2xvciBvZiBpdHMgY2x1c3RlciBhbmQgdXNlIHJnYiBmdW5jdGlvbiB0byBjb252ZXJ0IGl0IHRvIEhFWA0KYGBge3J9DQprQ29sb3VycyA8LSByZ2Ioa21lYW5zcmVzdWx0cyRjZW50ZXJzW3Bpdm90aW1hZ2UkQ2x1c3RlcixdKQ0KYGBgDQogIA0KVGhlbiBwbG90IGl0IHVzaW5nIGdncGxvdA0KYGBge3J9DQpnZ3Bsb3QoZGF0YSA9IHBpdm90aW1hZ2UsIGFlcyh4ID0geCwgeSA9IC15KSkgKyAgZ2VvbV9wb2ludChjb2xvdXIgPSBrQ29sb3VycykgKyBjb29yZF9maXhlZCgpDQpgYGANCg0KIzEwLiBJbnN0YWdyYW0tbGlrZSBmaWx0ZXI/IFdoeSBub3Q/DQpTbyBub3cgd2Uga25vdyBob3cgdG8gZmluZCBjZW50cm9pZHMgYW5kIGFwcGx5IGl0IHRvIHRoZSBpbWFnZS4gV2h5IG5vdCBtYWtpbmcgaXQgbW9yZSBJbnN0YWdyYW0tbGlrZSBhbmQgY2hvb3NlIG9uZSBjb2xvdXIgYW5kIG1ha2UgdGhlIHJldCBvZiB0aGUgaW1hZ2UgZ3JleXNjYWxlPw0KV2UgbmVlZCAgdG8gY2hvb3NlIG9uZSBjbHVzdGVyIC0gbWF5YmUgcmVkPyBTbyBudW1iZXIgNC4NCg0KTm93IHdlIHdpbGwgcmVjb2xvdXIgb3VyIGltYWdlIGxlYXZpbmcgcmVkIGFuZCB0dXJpbmluZyBldmVyeXRoaW5nIGVsc2Ugb250byBncmV5c2NhbGUuIEhvd2V2ZXIgZmlyc3Qgd2UgbmVlZCB0byBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHdpbGwgZGV0ZXJtaW5lIGl0IC0gaXQgd2lsbCBiZSBjYWxsZWQgImNvbG9yX29yX2dyZXkiDQogIA0KYGBge3J9DQpjbHVzdGVyTGFiZWwgPC0gNA0KZ3JleV9zY2FsZSA8LSBmdW5jdGlvbihjb2xvdXIpew0KICAgIGdyZXkgPC0gY29sb3VyWzFdICogMC4yMTI2ICsgY29sb3VyWzJdICogMC43MTUyICsgY29sb3VyWzNdICogMC4wNzIyDQogICAgcmV0dXJuKHJnYihncmV5LGdyZXksZ3JleSkpfQ0KIyMgdGhpcyBpcyBob3cgdGhlIGNvbG91ciBpcyBjb252ZXJ0ZWQgdG8gZ3JleXNjYWxlDQoNCmNvbG9yX29yX2dyZXkgPC0gZnVuY3Rpb24ocm93KXsNCiAgaWYocm93WyJDbHVzdGVyIl09PWNsdXN0ZXJMYWJlbCl7DQogICAgcmV0dXJuKHJnYihyb3dbIlIiXSxyb3dbIkciXSxyb3dbIkIiXSkpDQogIH0NCiAgZWxzZXsNCiAgICByZXR1cm4oZ3JleV9zY2FsZShhcy5udW1lcmljKHJvd1tjKCJSIiwiRyIsIkIiKV0pKSkNCiAgfQ0KfQ0KDQpwaXZvdGltYWdlJHNwbGFzaCA8LSBhcHBseShwaXZvdGltYWdlLDEsY29sb3Jfb3JfZ3JleSkNCiMjIFRoZW4gd2UgY2FuIGFzc2lnbiBhIG5ldyB2YXJpYWJsZSBhbmQgcnVuIHRoZSBhcHBseSBmdW5jdGlvbiB0byBjaGVjayBhbmQgY29udmVydCBpdCBmb3IgdXMgIA0KYGBgDQogIA0KYW5kIHBsb3QgaXQuLi4NCmBgYHtyfQ0KZ2dwbG90KGRhdGEgPSBwaXZvdGltYWdlLCBhZXMoeCA9IHgsIHkgPSAteSkpICsgIGdlb21fcG9pbnQoY29sb3VyID0gcGl2b3RpbWFnZSRzcGxhc2gpICsgY29vcmRfZml4ZWQoKQ0KYGBgDQoNCg==